package basic.courseLearn04.problem;

import org.junit.Test;
import basic.utils.CommonUtil;

import java.util.ArrayList;

//分割链表,分成小于区域,等于,大于区域,保证位序不变
public class SplitLinkList {
    private class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    @Test
    public void test(){
        ListNode head = new ListNode(3,
                new ListNode(1,
                        new ListNode(3,
                                new ListNode(4,
                                        new ListNode(4,
                                                new ListNode(7,
                                                        new ListNode(5)))))));

        int x = 3;
        ListNode result = solution_2(head, x);
        System.out.println(printLinkList(result));
    }

    //1. 利用三色国旗思想，将其转换为数组操作(不稳定,本题不适合)
    public ListNode solution_1(ListNode head, int x){
        ArrayList<Integer> list = new ArrayList<>();
        ListNode temp_1 = head;
        //1. 将链表中的元素存入ArrayList中
        while(temp_1!= null){
            list.add(temp_1.val);
            temp_1 = temp_1.next;
        }
        //2. 对list中的元素使用三色国旗进行分割
        Integer[] arr = list.toArray(new Integer[0]);
        arr = partition(arr,x);
        //3. 将ArrayList中的元素重新组成链表
        ListNode temp_2 = head;
        int index = 0;
        while(temp_2!= null){
            temp_2.val = arr[index];
            temp_2 = temp_2.next;
            index++;
        }
        return head;
    }

    //2. 设置小于部分头,小于部分尾,大于部分头,大于部分尾,等于部分头,等于部分尾,逐个遍历,最后将上述部分相连
    public ListNode solution_2(ListNode head, int x){
        ListNode lessHead=null ,lessTail=null;
        ListNode greaterHead=null ,greaterTail=null;
        ListNode equalHead=null ,equalTail=null;
        ListNode temp = head;
        int flag_1 = 0, flag_2 = 0,flag_3 = 0;
        while(temp!= null){

            if(temp.val < x){                   //小于部分
                if (flag_1==0){
                    lessHead=temp;
                }else {
                    lessTail.next=temp;
                }
                lessTail=temp;
                flag_1=1;
            }else if(temp.val > x){                 //大于部分
                if (flag_2==0){
                    greaterHead=temp;
                }else {
                    greaterTail.next=temp;
                }
                greaterTail=temp;
                flag_2=1;
            }else {                         //等于部分
                if (flag_3==0){
                    equalHead=temp;
                }else {
                    equalTail.next=temp;
                }
                equalTail=temp;
                flag_3=1;
            }
            temp=temp.next;
        }
        ListNode resultHead = null,resultTail = null;
        //拼接链表
        if(lessTail!=null){     //小于部分
            resultHead=lessHead;
            resultTail=lessTail;
        }
        if(equalTail!=null) {    //等于部分
            if(resultTail!=null){       //前部分存在
                resultTail.next=equalHead;
                resultTail=equalTail;
            }else {    //前部分不存在
                resultHead=equalHead;
                resultTail=equalTail;
            }
        }
        if(greaterTail!=null) {    //大于部分
            if(resultTail!=null){       //前部分存在
                resultTail.next=greaterHead;
                resultTail=greaterTail;
            }else {    //前部分不存在
                resultHead=greaterHead;
                resultTail=greaterTail;
            }
        }
        if (resultTail!=null){
            resultTail.next=null;
        }
        return resultHead;
    }



    public Integer[] partition(Integer[] arr, int x){
        int left = 0;
        int right = arr.length - 1;
        for(int i = 0; i <= right; i++){
            if(arr[i] < x){
                CommonUtil.swap(arr, i, left);
                left++;
            }else if(arr[i] > x){
                CommonUtil.swap(arr, i, right);
                right--;
                i--;
            }
        }
        return arr;
    }

    public static String printLinkList(ListNode head) {
        String res = "";
        while (head!=null) {
            res += head.val + "->";
            head=head.next;
        }
        return res;
    }
}
